1. Field of Invention
The present invention is related to digital video compression, and more specifically, to the efficient motion estimation method that results in the saving of computing times.
2. Description of Related Art
Digital video has been adopted in an increasing number of applications, which include video telephony, videoconferencing, surveillance system, VCD (Video CD), DVD, and digital TV. In the past almost two decades, ISO and ITU have separately or jointly developed and defined some digital video compression standards including MPEG-1, MPEG-2, MPEG-4, MPEG-7, H.261, H.263 and H.264. The success of development of the video compression standards fuels the wide applications. The advantage of image and video compression techniques significantly saves the storage space and transmission time without sacrificing much of the image quality.
Most ISO and ITU motion video compression standards adopt Y, Cb and Cr as the pixel elements, which are derived from the original R (Red), G (Green), and B (Blue) color components. The Y stands for the degree of “Luminance”, while the Cb and Cr represent the color difference been separated from the “Luminance”. In both still and motion picture compression algorithms, the 8×8 pixels “Block” based Y, Cb and Cr go through the similar compression procedure individually.
There are essentially three types of picture codings in the MPEG video compression standard as shown in FIG. 1. I-frame 11, the “Intra-coded” picture, uses the block of 8×8 pixels within the frame to code itself. P-frame 12, the “Predictive” frame, uses previous I-frame or P-frame as a reference to code the differences between frames. B-frame 13, the “Bi-directional” interpolated frame, uses previous I-frame or P-frame 12 as well as the next I-frame or P-frame 14 as references to code the pixel information. In the I-frame coding, all “Block” with 8×8 pixels go through the same compression procedure that is similar to JPEG, the still image compression algorithm. At the same time, the P-frame and B-frame have to code the differences between the targeted frame and the reference frames.
In the coding of the differences between frames, the first step is to find the difference of the targeted frame, followed by the coding of the difference. For some considerations including accuracy, performance, and coding efficiency, in some video compression standards, a frame is partitioned into macroblocks of 16×16 pixels to estimate the block difference and the block movement. Each macroblock within a frame has to find the “best match” macroblock in the previous frame or in the next frame. The mechanism of identifying the best match macroblock is called “Motion Estimation”. A searching range is commonly defined to limit the computing times in the “best match” block searching. The computing power hungered motion estimation is adopted to search for the “Best Match” candidates within a searching range for each macro block as described in FIG. 3. According to the MPEG standard, a macro block is composed of four 8×8 “blocks” of “Luma (Y)” and one, two, or four “Chroma (Cb and Cr)”. Since Luma and Chroma are closely associated, in the motion estimation, only Luma needs the mostion estimation, and the Chroma, Cb and Cr in the corresponding position copy the same MV of Luma. The Motion Vector, MV, represents the direction and displacement of the block movement. For example, an MV=(5, −3) stands for the block movement of 5 pixels right in X-axis and 3 pixel down in the Y-axis. Motion estimator searches for the best match macroblock within a predetermined searching range 33, 36. By comparing the mean absolute differences, MAD or sum of absolute differences, SAD, the macroblock with the least MAD or SAD is identified as the “best match” macroblock. Once the best match blocks are identified, the MV between the targeted block 35 and the best match blocks 34, 37 can be calculated and the differences between each block within a macro block can be coded accordingly. This kind of block difference coding technique is called “Motion Compensation”. In the procedure of the motion estimation and motion compensation, the higher accuracy of the best match block, the less bit number will be needed in the coding since the block difference can be smaller if the accuracy is higher.
FIG. 2 shows a prior art block diagram of the MPEG video compression, which is most commonly adopted by video compression IC and system suppliers. In the case of I-frame or I-type macro block coding, the MUX 221 selects the coming pixels 21 to directly go to the DCT 23 block, the Discrete Cosine Transform before the Quantization 25 step. The quantized DCT coefficients are packed as pairs of “Run-Length” code, which has patterns that will later be counted and be assigned code with variable length by the VLC encoder 27. The Variable Length Coding depends on the pattern occurrence. The compressed I-frame bit stream will then be reconstructed by the reverse route of compression procedure 29 and be stored in a reference frame buffer 26 as future frames' reference. In the case of a P-frame, B-frame or a P-type, or a B-type macro block coding, the macro block pixels are sent to the motion estimator 24 to compare with pixels within macroblock of previous frame for the searching of the best match macroblock. The Predictor 22 calculates the pixel differences between the targeted 8×8 block and the block within the best match macroblock of previous frame or next frame if B-type frame. The block difference is then fed into the DCT 23, quantization 25, and VLC 27 coding, which is the same procedure like the I-frame or I-type macroblock coding.
Since the motion estimation consumes most computing power in the video compression procedure, the speed up of the motion estimation benefits in the total video compression performance enhancement. Bad or inaccurate measurement of the motion vector, the MV, results in larger differences between the targeted macroblock and the so called “best match” macroblock to cause higher bit rate of the compressed bit stream. A higher bit rate causes longer time in transmitting the data and requires more storage device to save the data. A commonly used method of reducing the bit rate is to quantize the DCT coefficients by using coarser quantization scales, which will more or less degrade the image quality and trigger more artifacts. Therefore, the compression performance, image quality and bit rate, are mostly likely conflicting requirements in video compression and becomes tradeoffs in the video compression system design.